//
// Parked lot full of cars with one empty. Move all cars from their current
// position to their assigned position moving only one car at a time.  
//
#include <iostream>
#include <vector>
#include <ext/numeric>
#include <iterator>
#include <algorithm>
#include <map>

using namespace std;

typedef vector<unsigned> Unsigneds;
typedef map<unsigned,unsigned> UnsMap;

ostream &operator<<(ostream &o, Unsigneds us) {
    copy( us.begin(), us.end(), ostream_iterator<unsigned>( o, "   " ) );
    return o;
}

ostream &operator<<(ostream &o, UnsMap const &m) {
    for ( UnsMap::const_iterator it = m.begin();
	  m.end() != it; it++ ) {
	o << it->first << ":" << it->second << " ";
    }
    return o;
}

int main( int argc, char *argv[] ) {
    srand( time(NULL) );
    Unsigneds cars(10);
    iota( cars.begin(), cars.end(), 0 );
    random_shuffle( cars.begin(), cars.end() );

    cout << cars << endl;

    UnsMap lookup;
    for ( unsigned i = 0; i < cars.size(); i++ ) {
        lookup[ cars[i] ] = i;
    }

    for ( unsigned i = 0; i < cars.size(); i++ ) {
	// swap car 0 into space i
	unsigned n = lookup[0];
	swap( cars[i], cars[n] );
	swap( lookup[cars[i]], lookup[cars[n]]);

	// swap car i into space i
	n = lookup[i];
	swap( cars[i], cars[n] );
	swap( lookup[cars[i]], lookup[cars[n]]);
    }
    cout << cars << endl;

return 0;
}
